#include "../tools.h"

class Solution {
private:
    int n_, k_;
public:
    void dfs(int level, string& path, vector<int>& factorial, vector<bool>& flag){
        if(level > n_) return;

        int cnt = factorial[n_ - level];
        for(int i = 1; i <= n_; ++i){
            if(flag[i]) continue;

            if(cnt < k_){
                k_ -= cnt;
                continue;
            }

            path += to_string(i);
            flag[i] = true;
            dfs(level + 1, path, factorial, flag);
            return;
        }
    }
    string getPermutation(int n, int k) {
        n_ = n, k_ = k;
        vector<bool> flag(n + 1, false);
        vector<int>factorial(n + 1, 0);
        factorial[0] = 1;
        for(int i = 1; i <= n; ++i){
            factorial[i] = factorial[i - 1] * i;
        }

        string res = "";
        dfs(1, res, factorial, flag);
        return res;
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;
    int n, k;
    n = 3;
    k = 3;

    cout << sol.getPermutation(n, k);
    
    
    
    return 0;
}
